﻿// 4228. 八数码II.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/4231/

在一个 3×3
 的网格中，1∼8
 这 8
 个数字和一个 X 恰好不重不漏地分布在这 3×3
 的网格中。

例如：

1 2 3
X 4 6
7 5 8
在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。

把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。

现在，给你一个初始网格状态，并希望你将其变换为一个目标网格状态，请你找到所需行动次数最少的方案。

我们用一行字符串来描述一种网格状态。

例如，网格：

1 2 3
X 4 6
7 5 8
用 123X46758 来表示。

输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据占两行，第一行包含一个字符串表示初始网格状态，第二行包含一个字符串表示目标网格状态。

保证给定状态合法，并且一定有解。

输出格式
每组数据输出占两行，第一行输出 Case x: y，其中 x
 为组别编号（从 1
 开始），y
 为所需最少行动次数。

第二行输出具体行动方案，如果方案不唯一，则输出字典序最小的方案。

数据范围
1≤T≤200
输入样例：
2
12X453786
12345678X
564178X23
7568X4123
输出样例：
Case 1: 2
dd
Case 2: 8
urrulldr
*/
int main()
{
    std::cout << "Hello World!\n";
}

 